HackerRank Non-Divisible Subset

https://www.hackerrank.com/challenges/non-divisible-subset/problem

提出

code: python

#!/bin/python3

import math

import os

import random

import re

import sys

# Complete the 'nonDivisibleSubset' function below.

# The function is expected to return an INTEGER.

# The function accepts following parameters:

# 1. INTEGER k

# 2. INTEGER_ARRAY s

def nonDivisibleSubset(k, s):

# Write your code here

for i in range(len(s)):

si %= k

print(s)

if __name__ == '__main__':

fptr = open(os.environ'OUTPUT_PATH', 'w')

first_multiple_input = input().rstrip().split()

n = int(first_multiple_input0)

k = int(first_multiple_input1)

s = list(map(int, input().rstrip().split()))

result = nonDivisibleSubset(k, s)

fptr.write(str(result) + '\n')

fptr.close()

0 -> 1つしか足せない

https://scrapbox.io/files/61ca61128c38b500221256c0.png

1 -> 全部足せる

https://scrapbox.io/files/61ca6116fb541f001def8ef4.png

6 -> 全部足せない

https://scrapbox.io/files/61ca6118c980c2001fc4763c.png

1, 6で集合が大きい方を残す

https://scrapbox.io/files/61ca612702f22b001d4e92c7.png

https://scrapbox.io/files/61ca612af4099b0023ee6b39.png

2, 5で集合が大きい方を残す

https://scrapbox.io/files/61ca612d85cb9c00219f8b8a.png

3, 4で集合が大きい方を残す

https://scrapbox.io/files/61ca612ff4249c001d6557c0.png

kが偶数の場合

https://scrapbox.io/files/61ca613278f824001d20c581.png

https://scrapbox.io/files/61ca6135d2b75a001d454256.png

4 -> 0と同じ扱いで1つしか足せない

https://scrapbox.io/files/61ca6138f4249c001d6558a7.png

code: python

#!/bin/python3

import math

import os

import random

import re

import sys

# Complete the 'nonDivisibleSubset' function below.

# The function is expected to return an INTEGER.

# The function accepts following parameters:

# 1. INTEGER k

# 2. INTEGER_ARRAY s

def nonDivisibleSubset(k, s):

# Write your code here

f = 0 * k

for i in range(len(s)):

f[si%k]+=1

res = min(f0, 1)

for i in range(1, (k//2) + 1):

if (i != k-i):

res += max(fi, fk-i)

else:

# 0 or 1

res += min(fi, 1)

return res